{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Successor LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inorderSuccessor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #后继者"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一个算法，找出二叉搜索树中指定节点的&ldquo;下一个&rdquo;节点（也即中序后继）。</p>\n",
    "\n",
    "<p>如果指定节点没有对应的&ldquo;下一个&rdquo;节点，则返回<code>null</code>。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = <code>[2,1,3], p = 1\n",
    "\n",
    "  2\n",
    " / \\\n",
    "1   3\n",
    "</code>\n",
    "<strong>输出:</strong> 2</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = <code>[5,3,6,2,4,null,null,1], p = 6\n",
    "\n",
    "      5\n",
    "     / \\\n",
    "    3   6\n",
    "   / \\\n",
    "  2   4\n",
    " /   \n",
    "1\n",
    "</code>\n",
    "<strong>输出:</strong> null</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [successor-lcci](https://leetcode.cn/problems/successor-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [successor-lcci](https://leetcode.cn/problems/successor-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = None\n",
    "\n",
    "    def inorder(self, root, p):\n",
    "        if root is None: return root \n",
    "        node = self.inorder(root.left, p)\n",
    "        if node is not None: return node\n",
    "        if self.pre == p:\n",
    "            return root\n",
    "        self.pre = root\n",
    "        node = self.inorder(root.right, p)\n",
    "        if node is not None: return node\n",
    "        return None\n",
    "\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        return self.inorder(root, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        \n",
    "        target = None\n",
    "        res = None\n",
    "\n",
    "        def mid(node):\n",
    "            nonlocal target, res\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            mid(node.left)\n",
    "\n",
    "            if not target and node == p: # 找到了p点\n",
    "                target = p            \n",
    "            elif target and not res: # p之前找到了，但是后继还没赋值\n",
    "                res = node\n",
    "\n",
    "            mid(node.right)\n",
    "\n",
    "        \n",
    "        mid(root)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        succ = None\n",
    "        # 有右子树\n",
    "        if p.right: \n",
    "            succ = p.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "        # 无右子树\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                succ = node\n",
    "                node = node.left  # 也找左子树，找大于的第一个\n",
    "            else:\n",
    "                node = node.right\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        l = []\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                l.append((root.val,root))\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        idx = 0\n",
    "        while idx < len(l):\n",
    "            if l[idx][1] == p:\n",
    "                if idx + 1 < len(l):\n",
    "                    return l[idx+1][1]\n",
    "            idx += 1\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        st,pre,cur=[],None,root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur=cur.left\n",
    "            cur=st.pop()\n",
    "            if pre==p:\n",
    "                return cur\n",
    "            pre=cur\n",
    "            cur=cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if vec[0]:\n",
    "                vec[1] = root\n",
    "                vec[0] = False\n",
    "            if root is p:\n",
    "                vec[0] = True\n",
    "            dfs(root.right)\n",
    "\n",
    "        vec = [False, None]\n",
    "        dfs(root)\n",
    "        return vec[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        node=root\n",
    "        isp=False\n",
    "        result=None\n",
    "        stack=[]\n",
    "        while node!= None or len(stack)>0:\n",
    "            if node !=None :\n",
    "                stack.append(node)\n",
    "                node=node.left\n",
    "            else:\n",
    "                node=stack.pop()\n",
    "                print(node)\n",
    "                if(isp==True):\n",
    "                    result=node\n",
    "                    break\n",
    "                if(node==p):\n",
    "                    isp=True\n",
    "                node=node.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        def dfs(cur: TreeNode):\n",
    "            nonlocal ans\n",
    "            nonlocal prev\n",
    "            if cur:\n",
    "                dfs(cur.left)\n",
    "                if prev == p:\n",
    "                    ans = cur\n",
    "                prev = cur\n",
    "                dfs(cur.right)\n",
    "        \n",
    "        ans = prev = None\n",
    "        dfs(root)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # 中序遍历+二分查找法\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        def inorder(node):\n",
    "            if node is None:\n",
    "                return []\n",
    "            return inorder(node.left) + [node] + inorder(node.right)\n",
    "\n",
    "        arr = inorder(root)\n",
    "        for i, v in enumerate(arr):\n",
    "            arr[i] = v.val, i, v\n",
    "        n = len(arr)\n",
    "        idx = bisect_right(arr, (p.val, n, p))\n",
    "        return arr[idx][2] if idx < n else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if root is None or p is None: return\n",
    "        self.Flag=False\n",
    "        self.p_next=None\n",
    "        def dfs(root):\n",
    "            if root is None or self.p_next: return\n",
    "            dfs(root.left)\n",
    "            if root is p: self.Flag=True\n",
    "            if root is not p and self.Flag is True and self.p_next is None:\n",
    "                self.p_next=root\n",
    "                return\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.p_next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # 其实就是中序遍历 + 取出后一节点 + 考虑最右侧节点的后继为None\n",
    "        if root is None:\n",
    "            return None\n",
    "        stack, res = [], []\n",
    "        while stack or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                res.append(root)\n",
    "                root = root.right\n",
    "        index = 0\n",
    "        for i, node in enumerate(res):\n",
    "            if node == p:\n",
    "                index = i+1\n",
    "        if index < len(res):\n",
    "            return res[index]\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        flag=False\n",
    "        if not root:return \n",
    "        white,gray=0,1 \n",
    "        s=[[root,white]]\n",
    "        ls=[]\n",
    "        while s:\n",
    "            root,color=s.pop()\n",
    "            if flag:\n",
    "                return root\n",
    "            if root:\n",
    "                if color==white:\n",
    "                    s.append([root.right,white])\n",
    "                    s.append([root,gray])\n",
    "                    s.append([root.left,white])\n",
    "                else:\n",
    "                    ls.append([root.val,root])\n",
    "                        \n",
    "        for i,v in enumerate(ls):\n",
    "            if v[0]==p.val:\n",
    "                try:\n",
    "                    return  ls[i+1][1]\n",
    "                except:\n",
    "                    return \n",
    "                        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        st, pre, cur = [], None, root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = st.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        res = 0\n",
    "        flag = False\n",
    "        \n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal res, flag\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if flag:\n",
    "                res = root\n",
    "                flag = False\n",
    "            if root is p:\n",
    "                flag = True\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        cur = root\n",
    "        ans = None\n",
    "        while cur is not None:\n",
    "            if cur.val <=p.val:\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                ans = cur\n",
    "                cur = cur.left\n",
    "        return ans\n",
    "\n",
    "# [5,3,6,1,4,null,null,null,2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # 优化：之前的做法仅仅是中序遍历，并没有使用到搜索树的特性\n",
    "        # 二叉搜索树中的节点的后继节点，就是比它大的最小的那个\n",
    "        # 即若节点存在右子树，则需要找到右子树的最左节点，若无右子树，该最小值为进左子树时的父节点，如果始终进不了左子树则返回None\n",
    "        # 如果存在右树\n",
    "        if p.right:\n",
    "            cur = p.right\n",
    "            while cur.left:\n",
    "               cur = cur.left\n",
    "            return cur\n",
    "        # 否则需要从根节点root开始寻找\n",
    "        ans = None\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                ans = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        successor = None\n",
    "\n",
    "        if p.right:\n",
    "            successor = p.right\n",
    "            while successor.left:\n",
    "                successor = successor.left\n",
    "            return successor\n",
    "        \n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                successor = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return successor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # 法1: 中序遍历\n",
    "        # values = []\n",
    "        # def inOrder(root):\n",
    "        #     if not root: return\n",
    "        #     inOrder(root.left)\n",
    "        #     values.append(root)\n",
    "        #     inOrder(root.right)\n",
    "        # inOrder(root)\n",
    "        # for i, x in enumerate(values):\n",
    "        #     if x == p and i < len(values) - 1:\n",
    "        #         return values[i+1]\n",
    "        # return None\n",
    "\n",
    "        # 法2: 二叉搜索：\n",
    "        ans = None\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.val <= p.val:\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                ans = cur\n",
    "                cur = cur.left\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        res = None\n",
    "        flag = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            nonlocal flag\n",
    "            if root == None or res != None:\n",
    "                return \n",
    "\n",
    "            \n",
    "            \n",
    "            dfs(root.left)\n",
    "            if root == p:\n",
    "                flag = 1 \n",
    "            if root != p and flag == 1:\n",
    "                flag = 0\n",
    "                res = root   \n",
    "            dfs(root.right)\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # cur = root\n",
    "        # ans = None\n",
    "        # while cur is not None:\n",
    "        #     if cur.val <=p.val:\n",
    "        #         cur = cur.right\n",
    "        #     else:\n",
    "        #         ans = cur\n",
    "        #         cur = cur.left\n",
    "        # return ans\n",
    "        def get_node(node):\n",
    "            if node is None:\n",
    "                return []\n",
    "            return get_node(node.left) + [node] + get_node(node.right)\n",
    "        \n",
    "        ans = get_node(root) + [None]\n",
    "        for index in range(len(ans)):\n",
    "            if ans[index].val == p.val:\n",
    "                return ans[index + 1]\n",
    "\n",
    "# [5,3,6,1,4,null,null,null,2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        self.mark=0\n",
    "        self.p=p\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return \n",
    "            \n",
    "            item= inorder(root.left)\n",
    "            if item:\n",
    "                return item\n",
    "\n",
    "            if self.mark:\n",
    "                return root\n",
    "            else:\n",
    "                if root==self.p:\n",
    "                    self.mark=1\n",
    "\n",
    "            item=inorder(root.right)\n",
    "            if item:\n",
    "                return item\n",
    "\n",
    "        return inorder(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        while True:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            \n",
    "            root = stack.pop()\n",
    "            if root == p:\n",
    "                if not root.right:\n",
    "                    if not stack:   return None\n",
    "                    else:   return stack[-1]\n",
    "                root = root.right\n",
    "                while root.left:\n",
    "                    root = root.left\n",
    "                return root\n",
    "            root = root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        cur,res = root,None\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                res = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        stk = []\n",
    "        pre,cur = None, root\n",
    "        \n",
    "        while stk or cur:\n",
    "            while cur:\n",
    "                stk.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stk.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        parent, node = None, root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                parent, node = node, node.left\n",
    "            elif node.val < p.val:\n",
    "                node = node.right\n",
    "            elif node.right:\n",
    "                node = node.right\n",
    "                while node.left:\n",
    "                    node = node.left\n",
    "                return node\n",
    "            else:\n",
    "                return parent\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        st, pre, cur = [], None, root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = st.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        st, pre, cur = [], None, root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = st.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        f = False\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal f, ans\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            if f:\n",
    "                ans = root\n",
    "                f = False\n",
    "                return\n",
    "            if root == p:\n",
    "                f = True\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if root is None or p is None: return\n",
    "        self.Flag=False\n",
    "        self.p_next=None\n",
    "        def dfs(root):\n",
    "            if root is None or self.p_next: return\n",
    "            dfs(root.left)\n",
    "            if root is p: self.Flag=True\n",
    "            if root is not p and self.Flag is True and self.p_next is None:\n",
    "                self.p_next=root\n",
    "                return\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.p_next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        res = 0\n",
    "        flag = False\n",
    "        \n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal res, flag\n",
    "            if root is None:\n",
    "                return None\n",
    "            dfs(root.left)\n",
    "            if flag:\n",
    "                res = root\n",
    "                flag = False\n",
    "            if root is p:\n",
    "                flag = True\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode,count=0) -> TreeNode:\n",
    "        #找一个大于p的最小的值\n",
    "        parent,node =  None,root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                parent,node = node,node.left\n",
    "            elif node.val < p.val:\n",
    "                node = node.right\n",
    "            elif node.right:\n",
    "                node = node.right\n",
    "                while node.left:\n",
    "                    node = node.left\n",
    "                return node\n",
    "            else:\n",
    "                return parent\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        inorder = []\n",
    "        self.inorder(root, inorder)\n",
    "\n",
    "        # print(inorder)\n",
    "        idx = inorder.index(p)\n",
    "        if idx < len(inorder)-1:\n",
    "            return inorder[idx+1]\n",
    "        else:\n",
    "            return None \n",
    "\n",
    "    def inorder(self, root: TreeNode, res: List) -> None:\n",
    "        if root is None:\n",
    "            return \n",
    "        else:\n",
    "            self.inorder(root.left, res)\n",
    "            res.append(root)\n",
    "            self.inorder(root.right, res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    prev = None\n",
    "    ans = None\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if not root: return\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return\n",
    "\n",
    "            dfs(node.left)\n",
    "            if self.prev and self.prev.val == p.val:\n",
    "                self.ans = node\n",
    "            self.prev = node\n",
    "\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        if p.right :\n",
    "            ans = p.right\n",
    "            while ans.left:\n",
    "                ans = ans.left\n",
    "            return ans\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                ans = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        cur = root\n",
    "\n",
    "        found_p = False\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if found_p:\n",
    "                return cur\n",
    "            if cur == p:\n",
    "                found_p = True\n",
    "            cur = cur.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        pre = None\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            \n",
    "            cur = stack.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            root = cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        def zhong_search(tree: TreeNode,list_temp):\n",
    "            if tree is None:\n",
    "                return list_temp\n",
    "            else:\n",
    "                zhong_search(tree.left,list_temp)\n",
    "                list_temp.append(tree.val)\n",
    "                zhong_search(tree.right,list_temp)\n",
    "            return list_temp\n",
    "\n",
    "        ans=[]\n",
    "        res=zhong_search(root,ans)\n",
    "        if p.val in res and res.index(p.val)!=(len(res)-1):\n",
    "            return TreeNode(res[(res.index(p.val)+1)])\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        alist = []\n",
    "        self.visit(root, alist)\n",
    "        foundMatch = False\n",
    "        for node in alist:\n",
    "            if foundMatch:\n",
    "                return node\n",
    "            elif node is p:\n",
    "                foundMatch = True\n",
    "        return None\n",
    "\n",
    "    def visit(self, node, alist):\n",
    "        if node is None:\n",
    "            return\n",
    "        self.visit(node.left, alist)\n",
    "        alist.append(node)\n",
    "        self.visit(node.right, alist)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        arr = []\n",
    "        self.visit(root, p, arr)\n",
    "        if self.foundResult(p, arr):\n",
    "            return arr[-1]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "\n",
    "    def foundResult(self, p, arr):\n",
    "        return len(arr) > 1 and arr[-2] is p\n",
    "\n",
    "\n",
    "    def visit(self, node, p, arr):\n",
    "        if node is None or self.foundResult(p, arr):\n",
    "            return\n",
    "        \n",
    "        self.visit(node.left, p, arr)\n",
    "        \n",
    "        if self.foundResult(p, arr):\n",
    "            return\n",
    "        \n",
    "        arr.append(node)\n",
    "        \n",
    "        if self.foundResult(p, arr):\n",
    "            return\n",
    "        \n",
    "        self.visit(node.right, p, arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        successor = None\n",
    "        if p.right:\n",
    "            successor = p.right\n",
    "            while successor.left:\n",
    "                successor = successor.left\n",
    "            return successor\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                successor = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return successor\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        successer=None\n",
    "        if p.right:\n",
    "            successer=p.right\n",
    "            while successer.left:\n",
    "                successer=successer.left\n",
    "            return successer\n",
    "        node=root\n",
    "        while node:\n",
    "            if node.val>p.val:\n",
    "                successer=node\n",
    "                node=node.left\n",
    "            else:\n",
    "                node=node.right\n",
    "        return successer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        \n",
    "        pre = None\n",
    "        def dfs(root):\n",
    "            nonlocal pre\n",
    "            \n",
    "            if not root:\n",
    "                return None\n",
    "\n",
    "\n",
    "            lres = dfs(root.left)\n",
    "            if lres:\n",
    "                return lres\n",
    "\n",
    "\n",
    "            if pre == p:\n",
    "                return root\n",
    "            pre = root\n",
    "            \n",
    "            rres = dfs(root.right)\n",
    "            if rres:\n",
    "                return rres\n",
    "\n",
    "            return None\n",
    "\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        values = []\n",
    "        def inOrder(root):\n",
    "            if not root: return\n",
    "            inOrder(root.left)\n",
    "            values.append(root)\n",
    "            inOrder(root.right)\n",
    "        inOrder(root)\n",
    "        for i, x in enumerate(values):\n",
    "            if x == p and i < len(values) - 1:\n",
    "                return values[i+1]\n",
    "        return None\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        temp = root\n",
    "        succ = None\n",
    "        while temp is not None:\n",
    "            if temp.val <= p.val:\n",
    "                temp = temp.right\n",
    "            else:\n",
    "                succ = temp\n",
    "                temp = temp.left\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        inorder = []\n",
    "        self.inorder(root, inorder)\n",
    "        # print(inorder)\n",
    "        idx = inorder.index(p)\n",
    "        # print(idx)\n",
    "        if idx < len(inorder)-1:\n",
    "            return inorder[idx+1]\n",
    "        else:\n",
    "            return None \n",
    "\n",
    "    def inorder(self, root: TreeNode, res: List) -> None:\n",
    "        if root is None:\n",
    "            return \n",
    "        else:\n",
    "            self.inorder(root.left, res)\n",
    "            res.append(root)\n",
    "            self.inorder(root.right, res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        inorder = []\n",
    "        self.inorder(root, inorder)\n",
    "        # print(inorder)\n",
    "        idx = inorder.index(p)\n",
    "        # print(idx)\n",
    "        if idx < len(inorder)-1:\n",
    "            return inorder[idx+1]\n",
    "        else:\n",
    "            return None \n",
    "\n",
    "    def inorder(self, root: TreeNode, res: List) -> None:\n",
    "        if root is None:\n",
    "            return \n",
    "        else:\n",
    "            self.inorder(root.left, res)\n",
    "            res.append(root)\n",
    "            self.inorder(root.right, res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        st, pre, cur = [], None, root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = st.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        find=False\n",
    "        s=[]\n",
    "        q=root\n",
    "        while q or len(s)>0:\n",
    "            if q:\n",
    "                s.append(q)\n",
    "                q=q.left\n",
    "            else:\n",
    "                q=s.pop()\n",
    "                if find==True:\n",
    "                    return q\n",
    "                if q==p:\n",
    "                    find=True\n",
    "                q=q.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        self.first = TreeNode(float('-inf'))\n",
    "        self.second = None\n",
    "        self.idx = 0\n",
    "        self.ans = None\n",
    "        def dfs(node):\n",
    "            if self.ans != None:\n",
    "                return\n",
    "            if node == None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if self.idx == 0:\n",
    "                self.second = node\n",
    "                self.idx += 1\n",
    "            else:\n",
    "                self.first = self.second\n",
    "                self.second = node\n",
    "                self.idx += 1\n",
    "            if self.first.val == p.val:\n",
    "                self.ans = self.second\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        if self.second.val == p.val:\n",
    "            return None\n",
    "        else:\n",
    "            return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        cur = root\n",
    "        ans = None\n",
    "        if not root:\n",
    "            return None\n",
    "        if cur.val>p.val:\n",
    "            ans = self.inorderSuccessor(root.left, p)\n",
    "            return ans or root\n",
    "        else:\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        st, pre, cur = [], None, root\n",
    "        while st or cur:\n",
    "            while cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = st.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        successor=None\n",
    "        if p.right:\n",
    "            successor=p.right\n",
    "            while successor.left:\n",
    "                successor=successor.left\n",
    "            return successor\n",
    "        node=root\n",
    "        while node:\n",
    "            if node.val>p.val:\n",
    "                successor=node\n",
    "                node=node.left\n",
    "            else:\n",
    "                node=node.right\n",
    "        return successor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        cur,res = root,None\n",
    "\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                res = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        res = None\n",
    "        while root is not None:\n",
    "            if root.val <= p.val:\n",
    "                root = root.right\n",
    "            else:\n",
    "                res = root\n",
    "                root = root.left\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        self.p = p\n",
    "        self.res = None\n",
    "        self.last = None\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if root.left is not None:\n",
    "            self.dfs(root.left)\n",
    "\n",
    "        if self.last == self.p:\n",
    "            self.res = root\n",
    "\n",
    "        self.last = root\n",
    "        \n",
    "        if root.right is not None:\n",
    "            self.dfs(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = None\n",
    "    ans = None\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        def f(node, p):\n",
    "            # 边界条件\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            f(node.left, p)\n",
    "            if self.pre is p:\n",
    "                self.ans = node\n",
    "            self.pre = node\n",
    "            f(node.right, p)\n",
    "        \n",
    "        f(root, p)\n",
    "\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # cur = root\n",
    "        # ans = None\n",
    "        # while cur is not None:\n",
    "        #     if cur.val <=p.val:\n",
    "        #         cur = cur.right\n",
    "        #     else:\n",
    "        #         ans = cur\n",
    "        #         cur = cur.left\n",
    "        # return ans\n",
    "\n",
    "        # def get_node(node):\n",
    "        #     if node is None:\n",
    "        #         return []\n",
    "        #     return get_node(node.left) + [node] + get_node(node.right)\n",
    "        \n",
    "        # ans = get_node(root) + [None]\n",
    "        # for index in range(len(ans)):\n",
    "        #     if ans[index].val == p.val:\n",
    "        #         return ans[index + 1]\n",
    "\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val <= p.val:\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "        \n",
    "        ans = self.inorderSuccessor(root.left, p)\n",
    "        return root if ans is None else ans\n",
    "\n",
    "# [5,3,6,1,4,null,null,null,2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        return self.findSucc(root, p)\n",
    "\n",
    "    def findSucc(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        while root:\n",
    "            if root.val == p.val:\n",
    "                if root.right:\n",
    "                    p = root.right\n",
    "                    while p.left:\n",
    "                        p = p.left\n",
    "                    return p\n",
    "                break  # 这个break是需要的，因为这里有2个while  \n",
    "            elif p.val < root.val:\n",
    "                if ans is None or ans.val > root.val:\n",
    "                    ans = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        if root.val<=p.val:\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "        else:\n",
    "            ans = self.inorderSuccessor(root.left, p)\n",
    "            if ans:\n",
    "                return ans\n",
    "            else:\n",
    "                return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        arr = []\n",
    "        self.visit(root, p, arr)\n",
    "        if len(arr) > 1 and arr[-2] is p:\n",
    "            return arr[-1]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "\n",
    "    def visit(self, node, p, arr):\n",
    "        if node is None or (len(arr) > 1 and arr[-2] is p):\n",
    "            return\n",
    "        \n",
    "        self.visit(node.left, p, arr)\n",
    "        \n",
    "        if len(arr) > 1 and arr[-2] is p:\n",
    "            return\n",
    "        \n",
    "        arr.append(node)\n",
    "        \n",
    "        if len(arr) > 1 and arr[-2] is p:\n",
    "            return\n",
    "        \n",
    "        self.visit(node.right, p, arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        result = None\n",
    "        if p.right:\n",
    "            result = p.right\n",
    "            while result.left:\n",
    "                result = result.left\n",
    "            return result\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                result = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node  = node.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def get_next(self, root, array):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.get_next(root.left, array)\n",
    "        array.append(root)\n",
    "        self.get_next(root.right, array)\n",
    "        return\n",
    "        \n",
    "\n",
    "\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        results = []\n",
    "        self.get_next(root, results)\n",
    "        for i in range(len(results)):\n",
    "            if results[i]==p:\n",
    "                if i<len(results)-1:\n",
    "                    return results[i+1]\n",
    "                break\n",
    "        return None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        def findParent(root, p, parent):\n",
    "            if root == p:\n",
    "                return parent\n",
    "            if root.left:\n",
    "                return findParent(root.left, p, root)\n",
    "            if root.right:\n",
    "                return findParent(root.right, p, root)\n",
    "\n",
    "        def findSuccessor(root):\n",
    "            if not root.left: return root\n",
    "            findSuccessor(root.left)\n",
    "\n",
    "        data = []\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            data.append(root)\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        for i in range(len(data)-1):\n",
    "            if data[i] == p:\n",
    "                return data[i+1]\n",
    "\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            dfs(root.left)\n",
    "            res.append(root)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "\n",
    "        if res[-1] == p:\n",
    "            return\n",
    "        else:\n",
    "            return res[res.index(p) + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        return self.dfs_method(root, p)\n",
    "\n",
    "    def dfs_method(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        self.prev = None\n",
    "\n",
    "        def dfs(node: TreeNode) -> TreeNode | None:\n",
    "            if node is None:\n",
    "                return None\n",
    "\n",
    "            found = dfs(node.left)\n",
    "            if found:\n",
    "                return found\n",
    "            if self.prev is p:\n",
    "                return node\n",
    "            self.prev = node\n",
    "            return dfs(node.right)\n",
    "\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # 中序遍历（左根右）\n",
    "        lis=[]\n",
    "        def track(root):\n",
    "            if not root:\n",
    "                return\n",
    "            track(root.left)\n",
    "            lis.append(root)\n",
    "            track(root.right)\n",
    "        track(root)\n",
    "        i=lis.index(p)\n",
    "        return lis[i+1] if i!=len(lis)-1 else None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        # if not root:return None\n",
    "        # if root.val==p.val:\n",
    "        #     if not root.right:return None\n",
    "        #     cur = root.right\n",
    "        #     while cur.left:\n",
    "        #         cur = cur.left\n",
    "        #     return cur\n",
    "        # elif root.val>p.val:\n",
    "        #     res = self.inorderSuccessor(root.left,p)\n",
    "        #     return res if res!=None else root\n",
    "        # else:\n",
    "        #     return self.inorderSuccessor(root.right,p)\n",
    "        res = None\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.val>p.val:\n",
    "                res = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        pre = None\n",
    "        cur = root\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return None\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode: \n",
    "        A=[]\n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return \n",
    "            A.append(r.val)\n",
    "            dfs(r.left)\n",
    "            dfs(r.right)\n",
    "        dfs(root)\n",
    "        A.sort()\n",
    "        idx=A.index(p.val)\n",
    "        if idx==len(A)-1:\n",
    "            return None \n",
    "        res=A[idx+1]\n",
    "        ans=None\n",
    "        def dfs(r):\n",
    "            nonlocal ans\n",
    "            if not r:\n",
    "                return \n",
    "            if r.val==res:\n",
    "                ans=r \n",
    "            dfs(r.left)\n",
    "            dfs(r.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
